package com.clstu.linkedlist;

/**
 * 约瑟夫问题,用环形单链表解决,(丢手帕问题,围着一圈的人出圈)(多年前面试题)
 */
public class Josepfu {
    public static void main(String[] args) {
        //测试是否写对
        //创建环形链表
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        //添加数据
        circleSingleLinkedList.add(12);
        //查看结果
        circleSingleLinkedList.list();
        //测试出圈顺序
        circleSingleLinkedList.countBoy(10,20,12);
    }
}
/**
 * 一个单项环形链表类
 */
class CircleSingleLinkedList{
    //第一个位置
    private Boy first = null;

    //编写方法添加新的数据,根据传入的参数直接添加对应多个的数据
    public void add(int n){
        //校验数据
        if(n<1){
            System.out.println("数据不正确,失败");
            return;
        }
        //循环添加数据
        Boy helper = first;//指向链表的尾部
        for (int i = 0; i < n; i++) {
            Boy boy = new Boy(i + 1);
            //如果链表空
            if (first == null) {
                first = boy;
                //形成环状
                first.setNext(boy);
                helper = boy;//helper后移,指向尾部
                continue;
            }
            //插入数据
            helper.setNext(boy);
            boy.setNext(first);//形成环状
            //helper后移,指向尾部
            helper = boy;
        }
    }

    //编写方法遍历显示整个链表
    public void list(){
        //如果链表空
        if(first == null){
            System.out.println("环形链表中没有数据");
            return;
        }
        //遍历显示所有数据
        Boy helper = first;
        while (true){
            //显示数据
            System.out.println(helper);
            //如果遍历完
            if (helper.getNext() == first) {
                break;
            }
            //后移
            helper = helper.getNext();
        }
    }

    //编写方法根据传入参数列出出圈顺序
    /**
     *
     * @param start 从哪个位置开始报数
     * @param countNum 报到几就出圈
     * @param num 开始圈中的人数
     */
    public void countBoy(int start,int countNum,int num){
        //校验数据
        if(start<1 || start>num){
            System.out.println("数据不合法,失败");
            return;
        }
        //如果链表空
        if(first == null){
            System.out.println("链表空,失败");
            return;
        }
        //思路:
        // 1.定义辅助指针helper,并且让helper永远指向first的前一个(便于删除节点)
        // 2.first遍历到出圈位置的时候,就打印,同时删除节点.(删除节点必须利用helper的帮助)
        //定义helper,并且让其指向first的后一个位置
        Boy helper = first;
        while (true){
            //如果下一个节点是first
            if(helper.getNext()==first){
                break;
            }
            //后移
            helper = helper.getNext();
        }
        //遍历到start的位置
        for (int i = 0; i < start - 1; i++) {
            //helper和first同时后移
            first = first.getNext();
            helper = helper.getNext();
        }
        //循环出圈(输出并删除)
        while (true) {
            //如果最后只剩下一个小孩
            if(helper == first){
                break;
            }
            //报n个数
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println("第" + first.getId() + "个小孩出圈");
            helper.setNext(first.getNext());//first节点再无引用,会被垃圾回收机制回收
            first = helper.getNext();//first后移
        }
        //输出最后留在圈中的小孩
        System.out.println("最后留在圈中的孩子是:第"+first.getId()+"个小孩");
    }
}

/**
 * 一个节点类
 */
class Boy{
    private int id;
    private Boy next;
    //构造器
    public Boy(int id){
        this.id = id;
    }

    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    //重写toString方法

    @Override
    public String toString() {
        return "Boy{" +
                "id=" + id +
                '}';
    }
}